686E - Optimal Point - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=6e18,INF2=9e18;
const int NN=1e5+5;
int t,n;
ll sx[NN],sy[NN],sz[NN];
ll ansx,ansy,ansz;
void get_ans(ll a,ll b,ll c,ll r){
//	cout<<"The result is "<<a<<" "<<b<<" "<<c<<" "<<r<<'\n';
	ansx=b+c+r;
	ansy=a+c+r;
	ansz=a+b+r;
}
ll Ceil(ll x,ll div){
	if(x<0){
		return x/div;
	}else{
		return (x+1)/div;
	}
}
ll Floor(ll x,ll div){
	if(x<0){
		return (x-1)/div;
	}else{
		return x/div;
	}
}
bool check(ll d){
	ll l1=-INF2,l2=-INF2,l3=-INF2,l4=-INF2,r1=INF2,r2=INF2,r3=INF2,r4=INF2;
	for(int i=1;i<=n;i++){
		ll &x=sx[i],&y=sy[i],&z=sz[i];
//		cout<<"SUM "<<-d+x+y+z<<" "<<d+x+y+z<<'\n';
		l1=max(l1,-d+x+y+z);
		l2=max(l2,-d-x+y+z);
		l3=max(l3,-d+x-y+z);
		l4=max(l4,-d+x+y-z);
		r1=min(r1,d+x+y+z);
		r2=min(r2,d-x+y+z);
		r3=min(r3,d+x-y+z);
		r4=min(r4,d+x+y-z);
	}
//	cout<<l1<<" "<<l2<<" "<<l3<<" "<<l4<<'\n';
//	cout<<r1<<" "<<r2<<" "<<r3<<" "<<r4<<'\n';
//	cout<<l1/2<<" "<<r1/2<<'\n';
	for(int r=0;r<=1;r++){
		ll ll1,ll2,ll3,ll4,rr1,rr2,rr3,rr4;
		ll1=Ceil(l1-3*r,2);
		ll2=Ceil(l2-r,2);
		ll3=Ceil(l3-r,2);
		ll4=Ceil(l4-r,2);
		rr1=Floor(r1-3*r,2);
		rr2=Floor(r2-r,2);
		rr3=Floor(r3-r,2);
		rr4=Floor(r4-r,2);
//		cout<<r<<":"<<'\n';
//		cout<<ll1<<" "<<ll2<<" "<<ll3<<" "<<ll4<<'\n';
//		cout<<rr1<<" "<<rr2<<" "<<rr3<<" "<<rr4<<'\n'; 
		if((ll1>rr1)||(ll2>rr2)||(ll3>rr3)||(ll4>rr4)){
			continue;
		}
		ll now=ll2+ll3+ll4;
		ll a=ll2,b=ll3,c=ll4;
//		cout<<now<<" "<<rr1<<'\n';
		if(now>rr1){
			continue;
		}
//		cout<<"we are at 1"<<'\n';
//		cout<<a<<" "<<b<<" "<<c<<'\n';
		if(now<ll1){
//			cout<<"we are at 2"<<'\n';
			if(ll1-now<=rr2-ll2){
				a=ll2+(ll1-now);
				get_ans(a,b,c,r);
				return true;
			}else{
//				cout<<"we are at 3"<<'\n';
				a=rr2;
				now=a+b+c;
//				cout<<a<<" "<<b<<" "<<c<<'\n';
				if(ll1-now<=rr3-ll3){
					b=ll3+(ll1-now);
					get_ans(a,b,c,r);
					return true;
				}else{
//					cout<<"we are at 4"<<'\n';
					b=rr3;
					now=a+b+c;
//					cout<<a<<" "<<b<<" "<<c<<'\n';
//					cout<<"Step3 "<<a<<" "<<b<<" "<<c<<" "<<r<<'\n'; 
					if(ll1-now<=rr4-ll4){
						c=ll4+(ll1-now);
						get_ans(a,b,c,r);
						return true;
					}else{
//						cout<<now<<" "<<a<<" "<<b<<" "<<c<<" "<<ll1<<'\n'; 
//						cout<<"we are at 5"<<'\n';
						continue;
					}
				}
			}
		}else{
			get_ans(a,b,c,r);
			return true;
		}
	}
	return false;
}
int main(){
//	freopen("OP.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while(t){
		t--;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>sx[i]>>sy[i]>>sz[i];
		}
		ll L=-1,R=INF;
		while(L+1<R){
			ll mid=L+(R-L)/2;
//			cout<<L<<" "<<R<<" "<<mid<<'\n';
			if(check(mid)){
				R=mid;
			}else{
				L=mid;
			}
		}
		check(R);
//		cout<<R<<'\n';
		cout<<ansx<<" "<<ansy<<" "<<ansz<<'\n';
	}
	return 0;
}